{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Chunked Palindrome Decomposition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #two-pointers #string #dynamic-programming #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #双指针 #字符串 #动态规划 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestDecomposition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #段式回文"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你会得到一个字符串&nbsp;<code>text</code>&nbsp;。你应该把它分成 <code>k</code>&nbsp;个子字符串&nbsp;<code>(subtext1, subtext2，…， subtextk)</code>&nbsp;，要求满足:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>subtext<sub>i</sub></code><sub>&nbsp;</sub>是 <strong>非空&nbsp;</strong>字符串</li>\n",
    "\t<li>所有子字符串的连接等于 <code>text</code> ( 即<code>subtext<sub>1</sub>&nbsp;+ subtext<sub>2</sub>&nbsp;+ ... + subtext<sub>k</sub>&nbsp;== text</code>&nbsp;)</li>\n",
    "\t<li>对于所有 <font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.6px\"><span style=\"background-color:#f9f2f4\">i</span></span></font></font>&nbsp;的有效值( 即&nbsp;<code>1 &lt;= i&nbsp;&lt;= k</code> ) ，<code>subtext<sub>i</sub>&nbsp;== subtext<sub>k - i + 1</sub></code> 均成立</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<code>k</code>可能最大值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text = \"ghiabcdefhelloadamhelloabcdefghi\"\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>我们可以把字符串拆分成 \"(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text = \"merchant\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>我们可以把字符串拆分成 \"(merchant)\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text = \"antaprezatepzapreanta\"\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>我们可以把字符串拆分成 \"(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= text.length &lt;= 1000</code></li>\n",
    "\t<li><code>text</code>&nbsp;仅由小写英文字符组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-chunked-palindrome-decomposition](https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-chunked-palindrome-decomposition](https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ghiabcdefhelloadamhelloabcdefghi\"', '\"merchant\"', '\"antaprezatepzapreanta\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        c=re.compile(r'^(\\w+?)(\\w*)(\\1)$')\n",
    "        ans=1\n",
    "        while 1:\n",
    "            if not text:\n",
    "                return ans-1\n",
    "            temp=re.findall(c,text)\n",
    "            if not temp:\n",
    "                return ans\n",
    "            text=temp[0][1]\n",
    "            ans+=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 递归\n",
    "    def longestDecomposition(self, s: str) -> int:\n",
    "        # if text == \"\":\n",
    "        #     return 0\n",
    "        # for i in range(1, len(text) // 2 + 1): # 枚举前后缀长度\n",
    "        #     if text[:i] == text[-i:]: # 数组切片， 立刻分割\n",
    "        #         return 2 + self.longestDecomposition(text[i:-i])\n",
    "        # return 1 # 无法分割\n",
    "    \n",
    "    # 迭代\n",
    "        ans = 0\n",
    "        while s:\n",
    "            i = 1\n",
    "            while i <= len(s) // 2 and s[:i] != s[-i:]: # 枚举前后缀\n",
    "                i += 1\n",
    "            if i > len(s) // 2: #无法分割\n",
    "                ans += 1\n",
    "                break\n",
    "            ans += 2 # 分割出s[:i] 和s[-i:]\n",
    "            s = s[i : -i]\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 回溯\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        res1 = [] # 存储满足条件的字符串列表\n",
    "        res2 = [] # 存储满足条件的字符串长度列表\n",
    "        lis = []\n",
    "        def dfs(s):\n",
    "            if not s:\n",
    "                res1.append(''.join(lis)) # ['ghiihgabcdeffedcbahelloollehadammada']\n",
    "                res2.append(len(lis)) # [8]\n",
    "                return\n",
    "            pre1, pre2 = \"\", \"\"\n",
    "            length = len(s)\n",
    "            for i in range(length):\n",
    "                pre1 += s[i]\n",
    "                pre2 += s[length-i-1]\n",
    "                if pre1 == pre2[::-1]:\n",
    "                    lis.append(pre1)\n",
    "                    lis.append(pre2)\n",
    "                    dfs(s[i+1:length-1-i])\n",
    "                    break  # 减少搜索次数，因为只需寻找k最大可能值\n",
    "        dfs(text)\n",
    "        max_len = 0\n",
    "        for i in range(len(res1)):\n",
    "            if len(res1[i]) == len(text):\n",
    "                max_len = max(max_len, res2[i])\n",
    "            else: # 判断最中间字符串是否计数两次\n",
    "                max_len = max(max_len, res2[i] - 1)\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        high = text[-1]\n",
    "\n",
    "        count = 0\n",
    "        while len(text) > 0:\n",
    "            length = len(text)\n",
    "            pos_low = text.find(high, 0, length-1)\n",
    "            # print(pos_low)\n",
    "            if pos_low == -1:\n",
    "                count = count + 1\n",
    "                break\n",
    "            else:\n",
    "                while text[0:pos_low+1] != text[length-pos_low-1:length]:\n",
    "                    pos_low = text.find(high, pos_low+1, length)\n",
    "                    if pos_low == length-1:\n",
    "                        return 1\n",
    "                text = text[pos_low+1:length-pos_low-1]\n",
    "                count = count + 2\n",
    "                new_len = len(text)\n",
    "                if new_len > 0:\n",
    "                    high = text[new_len-1]\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 递归\n",
    "# class Solution:\n",
    "#     def longestDecomposition(self, text: str) -> int:\n",
    "#         n = len(text)\n",
    "#         if n <= 0:\n",
    "#             return 0\n",
    "#         for i in range(1, n // 2 + 1):\n",
    "#             if text[:i] == text[-i:]:\n",
    "#                 return 2 + self.longestDecomposition(text[i:-i])\n",
    "#         return 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        res = 0\n",
    "        while text:\n",
    "            i = 1\n",
    "            while i <= len(text) // 2 and text[:i] != text[-i:]:\n",
    "                i += 1\n",
    "\n",
    "            if i > len(text) // 2:\n",
    "                res += 1\n",
    "                break\n",
    "            res += 2\n",
    "            text = text[i:-i]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        l, r = 0, n-1\n",
    "        res = 0\n",
    "        while l <= r:\n",
    "            # 搜索区间合法时\n",
    "            i,j = l, r\n",
    "            # i,j 分别代表左右向心\n",
    "            oneComponent = True\n",
    "            while i < j:\n",
    "                #[l,i] [j,r]\n",
    "                # print(text[l:i+1],text[j:r+1])\n",
    "                if text[l:i+1] == text[j:r+1]:\n",
    "                    oneComponent = False\n",
    "                    break\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            # 如果break退出，\n",
    "            if i < j:\n",
    "                res += 2\n",
    "            else:\n",
    "                res += 1\n",
    "            l, r = i+1, j-1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        left,right = 0, n-1\n",
    "        left_s, right_s = 0, n\n",
    "        res = 0\n",
    "        while left < right:\n",
    "            while left < right and not text[left_s:left+1] == text[right:right_s]:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            if left < right and text[left_s:left+1] == text[right:right_s]:\n",
    "                res+=2\n",
    "                left_s, right_s = left+1, right\n",
    "            left+=1\n",
    "            right-=1\n",
    "        if left == right+1 and res>0:\n",
    "            res -= 1\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        i, j = 0, len(text)-1\n",
    "        count = 0\n",
    "        left = ''\n",
    "        right = ''\n",
    "        while i <= j:\n",
    "            left += text[i]\n",
    "            right = text[j] + right\n",
    "            if i == j:\n",
    "                break\n",
    "            else:\n",
    "                if left == right:\n",
    "                    left = ''\n",
    "                    right = ''\n",
    "                    count += 2\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if left != '' and right != '':\n",
    "            count += 1\n",
    "        return count\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/solution/duan-shi-hui-wen-by-leetcode-solution-vanl/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, s: str) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        while s:\n",
    "            i = 1\n",
    "            while i <= len(s) // 2 and s[:i] != s[-i:]:\n",
    "                i += 1\n",
    "            # 出来的情况也可能不满足\n",
    "            if i > len(s) // 2:\n",
    "                ans += 1\n",
    "                break\n",
    "            ans += 2\n",
    "            s = s[i:-i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, s: str) -> int:\n",
    "        i = 0\n",
    "        j = len(s)\n",
    "        f = True\n",
    "        r = 0\n",
    "\n",
    "        while f:\n",
    "            f = False\n",
    "\n",
    "            for k in range(1, ((j - i) >> 1) + 1):\n",
    "                if s[i : i + k] == s[j - k : j]:\n",
    "                    i += k\n",
    "                    j -= k\n",
    "                    r += 2\n",
    "                    f = True\n",
    "                    break\n",
    "\n",
    "        return r + (i != j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "\n",
    "        # https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/solutions/2221544/tu-jie-tan-xin-zuo-fa-yi-tu-miao-dong-py-huik/\n",
    "\n",
    "        # 贪心，从短到长，找到一组相同的前后缀，就算作一个分组，不需要找更长的，目的是找更多的分组，所以越短越好\n",
    "        res, s = 0, text\n",
    "        while s:\n",
    "            i, mid = 1, len(s) // 2\n",
    "            while i <= mid and s[:i] != s[-i:]: # 前半截，从1个字符开始逐渐增长，找相同的前后缀\n",
    "                i += 1\n",
    "            \n",
    "            if i > mid: # 循环没找到相同的前后缀，直接作为一个整体返回\n",
    "                res += 1\n",
    "                break\n",
    "            \n",
    "            # 找到一组相同的前后缀，结果+2，开始下一次循环\n",
    "            res += 2\n",
    "            s = s[i:-i]\n",
    "\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n=len(text)\n",
    "        l,r=0,n-1\n",
    "        i,j=0,n-1\n",
    "        count=0\n",
    "        while l<r:\n",
    "            if text[i:l+1]==text[r:j+1]:\n",
    "                count+=1\n",
    "                i=l+1\n",
    "                j=r-1\n",
    "            l+=1\n",
    "            r-=1\n",
    "        if i-j==1:\n",
    "            return count*2\n",
    "        else:\n",
    "            return 2*count+1\n",
    "    # def longestDecomposition(self, text):\n",
    "    #     \"\"\"\n",
    "    #     :type text: str\n",
    "    #     :rtype: int\n",
    "    #     \"\"\"\n",
    "    #     mul = 1\n",
    "    #     base = 25           #字符串哈希，一共26个字母>=26即可\n",
    "    #     mod = 10**7+1117    #大质数作为模减少碰撞和计算量\n",
    "    #     res = 0\n",
    "    #     l,r = 0,len(text)-1\n",
    "    #     number1,number2 = 0, 0\n",
    "    #     arr = [ord(c) - ord(\"a\") for c in text]     #存储encode结果，也可以到时候再算\n",
    "    #     while l < r:\n",
    "    #         number1 = (number1*base + arr[l])%mod   #从前往后计算哈希\n",
    "    #         number2 = (number2 + arr[r]*mul)%mod    #从后往前计算哈希\n",
    "    #         mul *= base%mod                         #这里本来是arr[r]**(base)^i次方，i是迭代次数，乘法比大的幂次计算节约时间\n",
    "    #         l += 1\n",
    "    #         r -= 1\n",
    "    #         if number1 == number2:                  #找到一组答案加二并重置\n",
    "    #             res += 2                            #必须重置，因为我们的计算规则\n",
    "    #             number1 = 0                         #如\"(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)\"。\n",
    "    #             number2 = 0                         #ant 和后面的 nta哈希值就不一样  nt和nt是一样的\n",
    "    #             mul = 1\n",
    "    #     if l == r:                                 #相等时剩最后一个中间字符，根据规则加1\n",
    "    #         res += 1\n",
    "    #     if number1 != number2 and l > r:           #l>r时如果number1=number2说明最后字符串刚好完全两两匹配\n",
    "    #         res += 1                               #如果不相等说明剩了一段没有匹配，要加1\n",
    "    #     return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        left, right = 0, len(text) - 1\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            n = right-left+1\n",
    "            pi = [0] * n\n",
    "            for i in range(1, n):\n",
    "                j = pi[i-1]\n",
    "                while j > 0 and text[left+i] != text[left+j]:\n",
    "                    j = pi[j-1]\n",
    "                if text[left+i] == text[left+j]:\n",
    "                    j += 1\n",
    "                pi[i] = j\n",
    "            if pi[-1] == 0:\n",
    "                return ans + 1\n",
    "            j = pi[-1]\n",
    "            while pi[j-1] > 0:\n",
    "                j = pi[j-1]\n",
    "            left += j\n",
    "            right -= j\n",
    "            ans += 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        res = 0\n",
    "        n = len(text)\n",
    "        while(n > 0):\n",
    "            n = len(text)\n",
    "            mid = n >> 1\n",
    "            token = True\n",
    "            for i in range(1, mid + 1):\n",
    "                if text[0:i] == text[-i:]:\n",
    "                    res += 2\n",
    "                    text = text[i:-i]\n",
    "                    token = False\n",
    "                    break\n",
    "            if token:\n",
    "                if n > 0:\n",
    "                    res += 1\n",
    "                    break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        # 左右各两个指针，判断头尾的子字符串是否相等\n",
    "        n = len(text)\n",
    "        left,right = 0, n-1\n",
    "        left_s, right_s = 0, n\n",
    "        res = 0\n",
    "        while left < right:\n",
    "            while left < right and not text[left_s:left+1] == text[right:right_s]:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            if left < right and text[left_s:left+1] == text[right:right_s]:\n",
    "                res+=2\n",
    "                left_s, right_s = left+1, right\n",
    "            left+=1\n",
    "            right-=1\n",
    "        if left == right+1 and res>0:\n",
    "            res -= 1\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        #双指针\n",
    "        n = len(text)\n",
    "        start= 0\n",
    "        end = n\n",
    "        k = 0\n",
    "        right = n-1#倒叙遍历指针\n",
    "        while start<right:\n",
    "            if text[right] == text[start]:#倒叙遍历找到第一个与start匹配的字符\n",
    "                length = end - right\n",
    "                if text[start:start+length] == text[right:end]:\n",
    "                    k += 2\n",
    "                    start = start+length\n",
    "                    end = right\n",
    "            right -= 1\n",
    "        if start < end:#k为奇数个，偶数时是start == end\n",
    "            k += 1\n",
    "        return k\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text) \n",
    "        l,r = 0 , n-1\n",
    "        res = 0\n",
    "        while l<=r:\n",
    "            p_n = 1\n",
    "            while l+p_n-1<r-p_n+1 and text[l:l+p_n] != text[r-p_n+1:r+1]:\n",
    "                p_n += 1\n",
    "            if l+p_n-1 >= r-p_n+1:\n",
    "                res += 1\n",
    "                break \n",
    "            else:\n",
    "                res += 2 \n",
    "                l = l+p_n \n",
    "                r = r-p_n \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestDecomposition(self, text: str) -> int:\r\n",
    "        i = 0\r\n",
    "        j = len(text) - 1\r\n",
    "        res = 0\r\n",
    "        while i < j:\r\n",
    "            # greedy, find the shortest common prefix and suffix\r\n",
    "            for l in range(1, (j - i + 1 >> 1) + 1):\r\n",
    "                for k in range(l):\r\n",
    "                    if text[i + k] != text[j - l + k + 1]:\r\n",
    "                        break\r\n",
    "                else:\r\n",
    "                    i += l\r\n",
    "                    j -= l\r\n",
    "                    res += 2\r\n",
    "                    break\r\n",
    "            else:\r\n",
    "                break\r\n",
    "\r\n",
    "        return res + (1 if i <= j else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        #双指针\n",
    "        n = len(text)\n",
    "        start= 0\n",
    "        end = n\n",
    "        k = 0\n",
    "        right = n-1\n",
    "        while start<right:\n",
    "            if text[right] == text[start]:\n",
    "                length = end - right\n",
    "                if text[start:start+length] == text[right:end]:\n",
    "                    k += 2\n",
    "                    start = start+length\n",
    "                    end = right\n",
    "            right -= 1\n",
    "        if start < end:\n",
    "            k += 1\n",
    "        return k\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        def get(l, r):\n",
    "            return (h[r] - h[l-1] * p[r - l + 1]) % mod\n",
    "        \n",
    "        n = len(text)\n",
    "        base = 131\n",
    "        mod = 10 ** 9 + 7\n",
    "        h = [0] * (n + 1)\n",
    "        p = [1] * (n + 1)\n",
    "\n",
    "        for i, c in enumerate(text):\n",
    "            t = ord(c) - ord('a') + 1\n",
    "            h[i + 1] = (h[i] * base) % mod + t\n",
    "            p[i + 1] = (p[i] * base) % mod\n",
    "        \n",
    "        ans = 0\n",
    "        i, j = 0, n-1\n",
    "\n",
    "        while i <= j:\n",
    "            k = 1\n",
    "            ok = False\n",
    "            while i + k - 1 < j - k + 1:\n",
    "                if get(i+1, i + k) == get(j - k + 2, j + 1):\n",
    "                    ans += 2\n",
    "                    i += k\n",
    "                    j -= k\n",
    "                    ok = True\n",
    "                    break\n",
    "                k += 1\n",
    "            if not ok:\n",
    "                ans += 1\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        dp = [0] * (n+1)\n",
    "\n",
    "        for i in range(1, n//2+1):\n",
    "            for j in range(i):\n",
    "                if text[j:i] == text[n-i:n-j] and (dp[j] > 0 or j == 0):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        if n % 2 == 0:\n",
    "            if dp[n//2] > 0:\n",
    "                return dp[n//2] * 2\n",
    "            else:\n",
    "                return (max(dp) * 2 + 1)\n",
    "        else:\n",
    "            return max(dp) * 2 + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        c=re.compile(r'^(\\w+?)(\\w*)(\\1)$')\n",
    "        ans=1\n",
    "        while 1:\n",
    "            print(text)\n",
    "            if not text:\n",
    "                return ans-1\n",
    "            temp=re.findall(c,text)\n",
    "            if not temp:\n",
    "                return ans\n",
    "            text=temp[0][1]\n",
    "            ans+=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        # sub0 = subk-1\n",
    "        # sub1 = subk-2\n",
    "        # 121\n",
    "        ans = 0\n",
    "        n = len(text)\n",
    "        left, right = 1, n-1\n",
    "        left_th, right_th = 0, n \n",
    "        while left <= right:\n",
    "            if text[left_th:left] == text[right:right_th]:\n",
    "                ans += 2\n",
    "                left_th = left\n",
    "                right_th = right\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        if left_th != right_th:\n",
    "            ans += 1\n",
    "        print(left, right)\n",
    "        print(left_th, right_th)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        def get(l, r):\n",
    "            return (p[r+1] - p[l] * mul[r - l +1]) % mod\n",
    "        n = len(text)\n",
    "        p = [0] * (n+1)\n",
    "        mul = [1] * (n+1)\n",
    "\n",
    "        base = 131\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            t = ord(text[i]) - ord('a')\n",
    "            p[i+1] = (p[i] * base + t) % mod\n",
    "            mul[i+1] = mul[i] * base % mod\n",
    "        \n",
    "        l, r = 0, n-1\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            k = 1\n",
    "            while l + k - 1 < r - k + 1 and get(l, l+k-1) != get(r-k+1, r):\n",
    "                k += 1\n",
    "            # 出来的情况可能是不满足\n",
    "            if l + k - 1 >= r - k + 1:\n",
    "                ans += 1\n",
    "                return ans\n",
    "            # 可能可以的\n",
    "            ans += 2\n",
    "            l += k\n",
    "            r -= k\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        head = 0\n",
    "        length = len(text)\n",
    "        k = 0\n",
    "        for i in range(0,length//2):\n",
    "            if (text[i] == text[length-head-1] and text[head:i+1] == text[length-i-1:length-head]):\n",
    "                print(text[head:i+1])\n",
    "                k += 2\n",
    "                head = i+1\n",
    "        if head < (length+1)//2:\n",
    "            k += 1\n",
    "        return k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        lengh_text = len(text)\n",
    "        i, j = 0, lengh_text - 1\n",
    "        k, t = 0, j\n",
    "        while i <= j:\n",
    "            while text[i] != text[j]:\n",
    "                if j < (i+t) // 2 + 1:\n",
    "                    return k + 1\n",
    "                else:\n",
    "                    j -= 1\n",
    "            if i == j:\n",
    "                return k + 1\n",
    "            if text[i:i+(t-j+1)] == text[j:t+1]:\n",
    "                k += 2\n",
    "                i += t - j + 1\n",
    "                j = lengh_text - 1 - i\n",
    "            else:\n",
    "                j -= 1\n",
    "                continue\n",
    "            t = j\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#段氏回文\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        ans,s=0,text\n",
    "        while s:\n",
    "            i=1\n",
    "            while i<=len(s)//2 and s[:i]!=s[-i:]:i+=1#枚举前后缀\n",
    "            if i>len(s)//2:#无法分割了\n",
    "                ans+=1\n",
    "                break\n",
    "            ans+=2\n",
    "            s=s[i:-i]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        k = 0\n",
    "        a, b = [], []\n",
    "        length = len(text)\n",
    "        for i in range(length // 2):\n",
    "            a.append(text[i]), b.append(text[-(i+1)])\n",
    "            if a == b[::-1]:\n",
    "                k += 2\n",
    "                a, b = [], []\n",
    "        if length % 2 != 0 or len(a) != 0:\n",
    "            k += 1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        i, j = 0, len(text)-1\n",
    "        count = 0\n",
    "        left = ''\n",
    "        right = ''\n",
    "        while i <= j:\n",
    "            left += text[i]\n",
    "            right = text[j] + right\n",
    "            if i == j:\n",
    "                break\n",
    "            else:\n",
    "                if left == right:\n",
    "                    left = ''\n",
    "                    right = ''\n",
    "                    count += 2\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if left != '' and right != '':\n",
    "            count += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n, ans = len(text), 0\n",
    "        prefix, suffix = [], []\n",
    "        for i in range(n // 2):\n",
    "            prefix.append(text[i])\n",
    "            suffix.append(text[-(i + 1)])\n",
    "            if prefix == suffix[::-1]:\n",
    "                ans += 2\n",
    "                prefix = []\n",
    "                suffix = []\n",
    "        return ans + 1 if n % 2 or len(prefix) else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, s: str) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        while s:\n",
    "            k = 1\n",
    "            while k <= len(s) // 2 and s[:k] != s[-k:]:\n",
    "                k += 1\n",
    "            # 可能不满足\n",
    "            if k > len(s) // 2:\n",
    "                ans += 1\n",
    "                break\n",
    "            ans += 2\n",
    "            s = s[k:-k]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        i, j = 0, len(text) - 1\n",
    "        count = 0\n",
    "        left = ''\n",
    "        right = ''\n",
    "        while i <= j:\n",
    "            left += text[i]\n",
    "            right = text[j] + right\n",
    "            if i == j:\n",
    "                break\n",
    "            else:\n",
    "                if left == right:\n",
    "                    left = ''\n",
    "                    right = ''\n",
    "                    count += 2\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if left != '' and right != '':\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        def get(l, r):\n",
    "            return (p[r+1] - p[l] * mul[r - l +1]) % mod\n",
    "        n = len(text)\n",
    "        p = [0] * (n+1)\n",
    "        mul = [1] * (n+1)\n",
    "\n",
    "        base = 131\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            t = ord(text[i]) - ord('a')\n",
    "            p[i+1] = (p[i] * base) % mod + t\n",
    "            mul[i+1] = mul[i] * base % mod\n",
    "        \n",
    "        l, r = 0, n-1\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            k = 1\n",
    "            while l + k - 1 < r - k + 1 and get(l, l+k-1) != get(r-k+1, r):\n",
    "                k += 1\n",
    "            # 出来的情况可能是不满足\n",
    "            if l + k - 1 >= r - k + 1:\n",
    "                ans += 1\n",
    "                return ans\n",
    "            # 可能可以的\n",
    "            ans += 2\n",
    "            l += k\n",
    "            r -= k\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        p = [0] * (n + 1)\n",
    "        mul = [1] * (n + 1)\n",
    "        base = 131\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        for i in range(n):\n",
    "            t = ord(s[i]) - ord('a')\n",
    "            p[i+1] = (p[i] * base + t) % mod\n",
    "            mul[i+1] = mul[i] * base % mod\n",
    "        \n",
    "        def get(l, r):\n",
    "            return (p[r+1] - p[l] * mul[r - l + 1]) % mod\n",
    "        \n",
    "        l, r = 0, n-1\n",
    "\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            k = 1\n",
    "            while l + k -1 < r - k + 1 and get(l, l + k - 1) != get(r-k+1, r):\n",
    "                k += 1\n",
    "            # 出来的可能不满足\n",
    "            if l + k - 1 >= r - k + 1:\n",
    "                ans += 1\n",
    "                break\n",
    "            ans += 2\n",
    "            l += k\n",
    "            r -= k\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        return next(\n",
    "            (2 + self.longestDecomposition(text[i: n - i]) for i in range(1, n // 2 + 1) if text[:i] == text[-i:]),\n",
    "            int(bool(text))\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        return next(\n",
    "            (2 + self.longestDecomposition(text[i: n - i]) for i in range(1, n // 2 + 1) if text[:i] == text[-i:]),\n",
    "            int(bool(text))\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        return next(\n",
    "            (2 + self.longestDecomposition(text[i: n - i]) for i in range(1, n // 2 + 1) if text[:i] == text[-i:]),\n",
    "            int(bool(text))\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "\n",
    "        if n % 2:\n",
    "            mid = (n >> 1) + 1\n",
    "        else:\n",
    "            mid = n >> 1\n",
    "            \n",
    "        # 0-8 12-20(n=21,mid=10)n - i + 1\n",
    "        for i in range(mid, n, 1):\n",
    "            if text[i] != text[0] :\n",
    "                continue\n",
    "            if text[i:] == text[0:n - i]:\n",
    "                return 2 * self.longestDecomposition(text[i:]) + self.longestDecomposition(text[n - i:i])\n",
    "        return 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        rtext=text[::-1]\n",
    "\n",
    "        n=len(text)\n",
    "        l=0\n",
    "        r=0\n",
    "        if n%2==0:\n",
    "            mid=n//2\n",
    "        else:\n",
    "            mid=n//2\n",
    "      # mid=n//2+1\n",
    "        cnt=0\n",
    "        for r in range(n):\n",
    "            print(r,mid,l)\n",
    "            if r<mid:\n",
    "                if text[l:r+1]==rtext[l:r+1][::-1]:\n",
    "                    l=r+1\n",
    "                    cnt+=2\n",
    "            if r>=mid:\n",
    "                if n%2==1:\n",
    "                    cnt+=1\n",
    "                elif r>l:\n",
    "                    cnt+=1\n",
    "                break\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        a = text\n",
    "        l = len(a)\n",
    "        if l == 1:\n",
    "            return 1\n",
    "        k = l//2\n",
    "        res = 0\n",
    "        i = 0\n",
    "        flag = True\n",
    "        while (i<k+1 and flag):\n",
    "            if i == k:\n",
    "                break\n",
    "            for j in range(i+1,k+2):\n",
    "                o = a[i:j]\n",
    "                p = a[l-j:l-i]\n",
    "                if a[i:j] == a[l-j:l-i] and i < l-j:\n",
    "                    print(a[i:j])\n",
    "                    res += 2\n",
    "                    i = j\n",
    "                    flag = True\n",
    "                    continue\n",
    "                if i <= l-j:\n",
    "                    flag = False\n",
    "        if not flag:\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "string hash: o(n)\n",
    "\"\"\"\n",
    "N = 10**5 + 10\n",
    "P, h, p = 131, [0] * N, [0] * N\n",
    "def get(l, r): return (h[r] - h[l - 1] * p[r - l + 1]) % (1<<64)\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int: \n",
    "        n = len(text)\n",
    "        p[0] = 1\n",
    "        for i in range(1, n + 1): \n",
    "            h[i] = (h[i - 1] * P + ord(text[i - 1])) % (1<<64)\n",
    "            p[i] = (p[i - 1] * P) % (1<<64)\n",
    "        l, r = 0, len(text) - 1 \n",
    "        res = 0 \n",
    "        while l <= r: \n",
    "            f = False \n",
    "            for i in range(1, (r - l + 1) // 2 + 1): \n",
    "                if get(l + 1, l + i) == get(r - i + 2, r + 1): \n",
    "                    l = l + i\n",
    "                    r = r - i\n",
    "                    f = True \n",
    "                    res += 2 \n",
    "                    break \n",
    "            if not f: \n",
    "                res += 1 \n",
    "                break\n",
    "        return res \n",
    "\"\"\"\n",
    "greedy: o(n2)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int: \n",
    "        l, r, res = 0, len(text) - 1, 0 \n",
    "        while l <= r: \n",
    "            f = False \n",
    "            for i in range(1, (r - l + 1) // 2 + 1): \n",
    "                if text[l: l + i] == text[r - i + 1: r + 1]:\n",
    "                    l = l + i\n",
    "                    r = r - i\n",
    "                    f = True \n",
    "                    res += 2 \n",
    "                    break \n",
    "            if not f: \n",
    "                res += 1 \n",
    "                break\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        ss = len(text)\n",
    "        st = 0\n",
    "        et = ss - 1\n",
    "\n",
    "        s_str = ''\n",
    "        e_str = ''\n",
    "\n",
    "        if ss == 1:\n",
    "            return 1\n",
    "\n",
    "        while (st < et):\n",
    "            \n",
    "            s_str += text[st]\n",
    "            e_str += text[et]\n",
    "            print('###: ', st, et, s_str, e_str[::-1])\n",
    "\n",
    "            if s_str == e_str[::-1]:\n",
    "                s_str = ''\n",
    "                e_str = ''\n",
    "                res += 2\n",
    "            else:\n",
    "                if st + 1 == et:\n",
    "                    res += 1\n",
    "                    break\n",
    "\n",
    "            if st + 2 == et:\n",
    "                res += 1     \n",
    "                break\n",
    "\n",
    "            st += 1\n",
    "            et -= 1\n",
    "            \n",
    "               \n",
    "        \n",
    "        return res\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        ss = len(text)\n",
    "        st = 0\n",
    "        et = ss - 1\n",
    "\n",
    "        s_str = ''\n",
    "        e_str = ''\n",
    "\n",
    "        if ss == 1:\n",
    "            return 1\n",
    "\n",
    "        while (st < et):\n",
    "            \n",
    "            s_str += text[st]\n",
    "            e_str += text[et]\n",
    "            print('###: ', st, et, s_str, e_str[::-1])\n",
    "\n",
    "            if s_str == e_str[::-1]:\n",
    "                s_str = ''\n",
    "                e_str = ''\n",
    "                res += 2\n",
    "            else:\n",
    "                if st + 1 == et:\n",
    "                    res += 1\n",
    "                    break\n",
    "\n",
    "            if st + 2 == et:\n",
    "                res += 1     \n",
    "                break\n",
    "\n",
    "            st += 1\n",
    "            et -= 1\n",
    "            \n",
    "               \n",
    "        \n",
    "        return res\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, s: str) -> int:\n",
    "        if s == \"\":\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            if s[:i] == s[-i:]:\n",
    "                return 2 + self.longestDecomposition(s[i:-i])\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n=len(text)\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==j:\n",
    "                return 1\n",
    "            if i>j:\n",
    "                return 0\n",
    "            return max([dfs(i+k,j-k)+2 for k in range(1,(j-i+1)//2+1) if text[i:i+k]==text[j-k+1:j+1]]+[1])\n",
    "        \n",
    "        return dfs(0,n-1)\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        ss = len(text)\n",
    "        st = 0\n",
    "        et = ss - 1\n",
    "\n",
    "        s_str = ''\n",
    "        e_str = ''\n",
    "\n",
    "        if ss == 1:\n",
    "            return 1\n",
    "\n",
    "        while (st < et):\n",
    "            \n",
    "            s_str += text[st]\n",
    "            e_str += text[et]\n",
    "            print('###: ', st, et, s_str, e_str[::-1])\n",
    "\n",
    "            if s_str == e_str[::-1]:\n",
    "                s_str = ''\n",
    "                e_str = ''\n",
    "                res += 2\n",
    "            else:\n",
    "                if st + 1 == et:\n",
    "                    res += 1\n",
    "                    break\n",
    "\n",
    "            if st + 2 == et:\n",
    "                res += 1     \n",
    "                break\n",
    "\n",
    "            st += 1\n",
    "            et -= 1\n",
    "            \n",
    "               \n",
    "        \n",
    "        return res\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, s: str) -> int:\n",
    "        if s == \"\":\n",
    "            return 0\n",
    "        for i in range(1, len(s) // 2 + 1):\n",
    "            if s[:i] == s[-i:]:\n",
    "                return 2 + self.longestDecomposition(s[i:-i])\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "\n",
    "\n",
    "        def recrusion(start, end):\n",
    "            if start == end: return 1\n",
    "            if start > end: return 0\n",
    "\n",
    "            for step in range(1, ((end - start) // 2) + 2):\n",
    "\n",
    "                if text[start: start + step] == text[end - step+1:end+1]:\n",
    "                    return recrusion(start + step, end - step) +2\n",
    "\n",
    "            return 1\n",
    "        \n",
    "        return recrusion(0, len(text)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n=len(text)\n",
    "        l,r=0,n-1\n",
    "        i,j=0,n-1\n",
    "        ret=0\n",
    "        while i<=j:\n",
    "            print(i,j,l,r)\n",
    "            print(text[l:i+1],text[j:r+1])\n",
    "            if text[l:i+1]==text[j:r+1]:\n",
    "                if i==j:\n",
    "                    #ret+=1\n",
    "                    return ret*2+1\n",
    "                ret+=1\n",
    "                i+=1\n",
    "                j-=1\n",
    "                l=i\n",
    "                r=j\n",
    "            else:\n",
    "                i+=1\n",
    "                j-=1\n",
    "        if l!=i:\n",
    "            ret+=1\n",
    "            return ret*2-1\n",
    "        return ret*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            if text[:i] == text[-i:]:\n",
    "                return 2 + self.longestDecomposition(text[i:-i])\n",
    "        return 1\n",
    "\n",
    "\n",
    "# 递归\n",
    "# class Solution:\n",
    "#     def longestDecomposition(self, text: str) -> int:\n",
    "#         n = len(text)\n",
    "#         if n <= 0:\n",
    "#             return 0\n",
    "#         for i in range(1, n // 2 + 1):\n",
    "#             if text[:i] == text[-i:]:\n",
    "#                 return 2 + self.longestDecomposition(text[i:-i])\n",
    "#         return 1\n",
    "\n",
    "# 迭代\n",
    "# class Solution:\n",
    "#     def longestDecomposition(self, text: str) -> int:\n",
    "#         res = 0\n",
    "#         while text:\n",
    "#             i = 1\n",
    "#             n = len(text) // 2\n",
    "#             while i <= n and text[:i] != text[-i:]:\n",
    "#                 i += 1\n",
    "#             if i > n:\n",
    "#                 res += 1\n",
    "#                 break\n",
    "#             res += 2\n",
    "#             text = text[i:-i]\n",
    "#         return res\n",
    "\n",
    "# 从后往前找首字母出现的位置，判断是否为前后相同的的字段，如果是就切割出来继续判断剩下的\n",
    "# class Solution:\n",
    "#     def longestDecomposition(self, text: str) -> int:\n",
    "#         n, ans = len(text), 0\n",
    "#         prefix, suffix = [], []\n",
    "#         for i in range(n // 2):\n",
    "#             prefix.append(text[i])\n",
    "#             suffix.append(text[-(i + 1)])\n",
    "#             if prefix == suffix[::-1]:\n",
    "#                 ans += 2\n",
    "#                 prefix = []\n",
    "#                 suffix = []\n",
    "#         return ans + 1 if n % 2 or len(prefix) else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "\n",
    "        # https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/solutions/2221544/tu-jie-tan-xin-zuo-fa-yi-tu-miao-dong-py-huik/\n",
    "\n",
    "        # 贪心，从短到长，找到一组相同的前后缀，就算作一个分组，不需要找更长的，目的是找更多的分组，所以越短越好\n",
    "\n",
    "        if text == \"\":\n",
    "            return 0\n",
    "        \n",
    "        for i in range(1, len(text)//2 + 1): # 前半截，从1个字符开始逐渐增长，找相同的前后缀\n",
    "            if text[:i] == text[-i:]:\n",
    "                return 2 + self.longestDecomposition(text[i:-i])\n",
    "        \n",
    "        # 循环没找到相同的前后缀，直接作为一个整体返回\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        if len(text) <= 1:\n",
    "            return len(text)\n",
    "        for i in range(len(text) // 2 + 1):\n",
    "            if text[:i] == text[-i:]:\n",
    "                return 2+self.longestDecomposition(text[i:-i])\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        if len(text) <= 1:\n",
    "            return len(text)\n",
    "        for i in range(1, len(text) // 2 + 1):\n",
    "            if text[:i] == text[-i:]:\n",
    "                return 2 + self.longestDecomposition(text[i: -i])\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        if len(text) <= 1:\n",
    "            return len(text)\n",
    "        for i in range(1, len(text) // 2 + 1):\n",
    "            if text[:i] == text[-i:]:\n",
    "                return 2 + self.longestDecomposition(text[i: -i])\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, s: str) -> int:\n",
    "        if s == \"\":\n",
    "            return 0\n",
    "        for i in range(1, len(s) // 2 + 1):  # 枚举前后缀长度\n",
    "            if s[:i] == s[-i:]:  # 立刻分割\n",
    "                return 2 + self.longestDecomposition(s[i:-i])\n",
    "        return 1  # 无法分割\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n=len(text)\n",
    "        dp=[-1]*n\n",
    "        def dfs(l,r):\n",
    "            if dp[l]>=0:\n",
    "                return dp[l]\n",
    "            # print(l,r)\n",
    "            if l==r: return 1\n",
    "            elif l>r: return 0\n",
    "            res=1\n",
    "            for i in range(1,n//2-l+1):\n",
    "                if text[l:l+i]==text[r-i+1:r+1]:\n",
    "                    res=max(res,dfs(l+i,r-i)+2)\n",
    "                # print(res)\n",
    "            dp[l]=res\n",
    "            return res\n",
    "        return dfs(0,n-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        @cache\n",
    "        def getcount(left,right):\n",
    "            if right==left:\n",
    "                return 1\n",
    "            elif right<left:\n",
    "                return 0\n",
    "            ans=1\n",
    "            for lenth in range(1,(right-left+1)//2+1):\n",
    "                if text[left:left+lenth]==text[right-lenth+1:right+1]:\n",
    "                    subans=getcount(left+lenth,right-lenth)\n",
    "                    ans=max(ans,2+subans)\n",
    "            return ans\n",
    "        return getcount(0,len(text)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        if text=='':\n",
    "            return 0\n",
    "        for i in range(1, len(text)//2+1):\n",
    "            if text[:i] == text[-i:]:\n",
    "                text = text[i:-i]\n",
    "                return 2 + self.longestDecomposition(text)\n",
    "        return 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        s, e = 0, len(text)\n",
    "        ans = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j - i < 1:\n",
    "                return j - i + 1\n",
    "            k = 1\n",
    "            curmax = 1\n",
    "            while i+k <= j-k+1:\n",
    "                if text[i:i+k] == text[j-k+1:j+1]:\n",
    "                    res = dfs(i+k, j-k) + 2\n",
    "                    # print(text[i:i+k], text[j-k+1:j+1], res)\n",
    "                    curmax = max(res, curmax)\n",
    "                k += 1\n",
    "            return curmax\n",
    "        \n",
    "        ans = dfs(s, e-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        def a(text, count):\n",
    "            if text=='':\n",
    "                return count\n",
    "            str_len = len(text)\n",
    "            for i in range(str_len//2):\n",
    "                end_str = text[-1-i:]\n",
    "                start_str = text[0:i+1]\n",
    "                if start_str == end_str:\n",
    "                    text = text[i+1:-i-1]\n",
    "                    count += 2\n",
    "                    return a(text, count)\n",
    "            return count + 1\n",
    "        return a(text, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        str_len = len(text)\n",
    "        def a(text, count):\n",
    "            if text=='':\n",
    "                return count\n",
    "            str_len = len(text)\n",
    "            is_match = False\n",
    "            for i in range(str_len//2):\n",
    "                end_str = text[-1-i:]\n",
    "                start_str = text[0:i+1]\n",
    "                if start_str == end_str:\n",
    "                    text = text[i+1:-i-1]\n",
    "                    is_match = True\n",
    "                    break\n",
    "                pass\n",
    "            if is_match:\n",
    "                count += 2\n",
    "                return a(text, count)\n",
    "            else:\n",
    "                return count + 1\n",
    "        res = a(text, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        if text == \"\":\n",
    "            return 0\n",
    "        \n",
    "        for i in range(1, len(text) // 2 + 1):\n",
    "            if text[:i] == text[-i:]:\n",
    "                return 2 + self.longestDecomposition(text[i:-i])\n",
    "        return 1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        s, e = 0, len(text)\n",
    "        ans = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j - i < 1:\n",
    "                return j - i + 1\n",
    "            k = 1\n",
    "            curmax = 1\n",
    "            while i+k <= j-k+1:\n",
    "                if text[i:i+k] == text[j-k+1:j+1]:\n",
    "                    res = dfs(i+k, j-k) + 2\n",
    "                    # print(text[i:i+k], text[j-k+1:j+1], res)\n",
    "                    curmax = max(res, curmax)\n",
    "                    return curmax\n",
    "                k += 1\n",
    "            return curmax\n",
    "        \n",
    "        ans = dfs(s, e-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 递归\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        if text == \"\":\n",
    "            return 0\n",
    "        for i in range(1, len(text) // 2 + 1): # 枚举前后缀长度\n",
    "            if text[:i] == text[-i:]: # 立刻分割\n",
    "                return 2 + self.longestDecomposition(text[i:-i])\n",
    "        return 1 # 无法分割\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        if text == \"\":\n",
    "            return 0\n",
    "        for i in range(1, len(text) // 2 + 1):  # 枚举前后缀长度\n",
    "            if text[:i] == text[-i:]:  # 立刻分割\n",
    "                return 2 + self.longestDecomposition(text[i:-i])\n",
    "        return 1  # 无法分割"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        if text == \"\":\n",
    "            return 0\n",
    "\n",
    "        lenS = (len(text) >> 1) + 1\n",
    "        for i in range(0, lenS):\n",
    "            if text[:i] == text[-i:]:\n",
    "                return 2 + self.longestDecomposition(text[i:-i])\n",
    "\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        def a(text, count):\n",
    "            if text=='':\n",
    "                return count\n",
    "            str_len = len(text)\n",
    "            for i in range(str_len//2):\n",
    "                end_str = text[-1-i:]\n",
    "                start_str = text[0:i+1]\n",
    "                if start_str == end_str:\n",
    "                    text = text[i+1:-i-1]\n",
    "                    count += 2\n",
    "                    return a(text, count)\n",
    "            return count + 1\n",
    "        return a(text, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        def dfs(s):\n",
    "            if not s:\n",
    "                return 0\n",
    "            l, r = 0, len(s) - 1\n",
    "            s1, s2 = \"\", \"\"\n",
    "            while l < r:\n",
    "                s1 += s[l]\n",
    "                s2 = s[r] + s2\n",
    "                if s1 == s2:\n",
    "                    return 2 + dfs(s[l+1:r])\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return 1\n",
    "\n",
    "        return dfs(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        \n",
    "\n",
    "        def dfs(s):\n",
    "            if s == '':\n",
    "                return 0\n",
    "            for i in range(1, len(s) // 2 + 1):\n",
    "                if s[:i] == s[-i:]:\n",
    "                    return 2 + dfs(s[i:-i])\n",
    "            return 1\n",
    "        \n",
    "        return dfs(text)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        for i in range(1, n//2 + 1):\n",
    "            if text[:i] == text[n-i:n]:\n",
    "                return 2 + self.longestDecomposition(text[i:n-i])\n",
    "        return 0 if n == 0 else 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        s, e = 0, len(text)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j - i < 1:\n",
    "                return j - i + 1\n",
    "            k = 1\n",
    "            while i+k <= j-k+1:\n",
    "                if text[i:i+k] == text[j-k+1:j+1]:\n",
    "                    res = dfs(i+k, j-k) + 2\n",
    "                    return res\n",
    "                k += 1\n",
    "            return 1\n",
    "\n",
    "        return dfs(s, e-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "\n",
    "        def dfs(s):\n",
    "            if s == '':\n",
    "                return 0\n",
    "            for k in range(1, len(s) // 2 + 1):\n",
    "                if s[:k] == s[-k:]:\n",
    "                    return 2 + dfs(s[k:-k])\n",
    "            return 1\n",
    "        \n",
    "        return dfs(text)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "\n",
    "        def alg(newText: str, ans: int):\n",
    "            str_len = len(newText)\n",
    "            start = 0\n",
    "            end = str_len\n",
    "            num = int(str_len/2)\n",
    "            for i in range(1, int(str_len/2)+1):\n",
    "                left = newText[start:start+i]\n",
    "                right = newText[end-i:end]\n",
    "                if left == right:\n",
    "                    ans = alg(newText[start+i:end-i], ans) + 2\n",
    "                    if newText[start + i:end - i] == '':\n",
    "                        ans = ans - 1\n",
    "                    break\n",
    "\n",
    "            return ans\n",
    "        return alg(text, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDecomposition(self, text: str) -> int:\n",
    "        n = len(text)\n",
    "        if not n:\n",
    "            return 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        mul = 1 \n",
    "        base = 131 \n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n // 2):\n",
    "            left = (left * base + ord(text[i]) - ord('a')) % mod\n",
    "            right = ((ord(text[n - i - 1]) - ord('a')) * mul + right) % mod\n",
    "            mul = mul * base % mod\n",
    "            if left == right:\n",
    "                return 2 + self.longestDecomposition(text[i + 1 : n - i - 1])\n",
    "        return 1 \n",
    "\n",
    "         "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
